#include <stdio.h>
#include <stdlib.h>

/******************************************************************************************
 * Implementacao do problema da mochila booleana adaptado para o problema das desculpas   *
 *                                                                                        *
 * @param weights os pesos                                                                *
 * @param values os valores                                                               *
 * @param capacity a capacidade da mochila                                                *
 * @param objectsAmount a quantidade de objetos                                           *
 *                                                                                        *
 * @see http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/solucoes/mochila-bool2.html *
 *                                                                                        *
 * @return a qua a quantidade de desculpas                                                *
 ******************************************************************************************/
int booleanKnapsackAdapted(int* weights, int* values, int capacity, int objectsAmount) {
    int t[objectsAmount + 1][capacity + 1];

    int b = 0;
    for (b = 0; b <= capacity; b++) {
        t[0][b] = 0;
        int i = 0;
        for (i = 1; i <= objectsAmount; i++) {
            int a = t[i - 1][b];
            int aLine = weights[i - 1] > b ? 0 : t[i - 1][b - weights[i - 1]] + values[i - 1];
            t[i][b] = a > aLine ? a : aLine;
        }
    }

    b = capacity;
    int sorriesAmount = 0;

    int i = 0;
    for (i = objectsAmount; i > 0; i--) {
        if (t[i][b] != t[i - 1][b]) {
            sorriesAmount += values[i - 1];
            b -= weights[i - 1];
        }
    }

    return sorriesAmount;
}

/********************************************************************************
 * Problema da disciplina de Estrutura de Dados e Complexidade de Algoritmos da *
 * Pos Graduacao do Periodo 2011.1                                              *
 *                                                                              *
 * @see http://br.spoj.pl/problems/DESCULPA/                                    *
 * @author Elenilson Vieira - 111100371 - elenilson[at]elenilsonvieira.com      *
 * @since 1 de junho de 2011                                                    *
 ********************************************************************************/
int main2(int argc, char** argv) {

    int testNumber = 1;

    /*** Pega sequencia de comandos e executa ***/
    int c = 0;
    int f = 0;
    while (scanf("%d %d", &c, &f) && c != 0 || f != 0) {
        int sorryAmountOnCard = -1;
        int cardSize = c;
        int phrasesAmount = f;
        int charsAmountOnPhrases[phrasesAmount];
        int sorryAmountOnPhrases[phrasesAmount];

        int n = 0;
        int d = 0;
        int i = 0;
        for (i = 0; i < phrasesAmount; i++) {
            scanf("%d %d", &n, &d);
            charsAmountOnPhrases[i] = n;
            sorryAmountOnPhrases[i] = d;
        }

        sorryAmountOnCard = booleanKnapsackAdapted(charsAmountOnPhrases, sorryAmountOnPhrases, cardSize, phrasesAmount);
        printf("Teste %d\n%d\n", testNumber++, sorryAmountOnCard);
    }

    return (EXIT_SUCCESS);
}


